#pragma once

/// 单链表类型定义

template <typename E>
struct LNode
{
    E data;
    LNode *next;
};

//typedef LNode *LinkList; // C
template <typename E>
using LinkList = LNode<E> *;

//单链表基本操作

///初始化空表 InitList（&L）
template <typename E>
void InitList(LinkList<E> &L)
{
    L = new LNode<E>;
    L->next = nullptr;
}

///链表插入
template <typename E>
void ListInsert(LinkList<E> &L, int i, E e)
{
    //查找第 i-1 的节点 p
    //Linklist<E> p-l;
    auto p = L;
    int j = 0;

    while (p && j < i - 1)
        p = p->next, ++j;

    //若找到，则在p之后插入额e，抛出异常
    if (p && j == i - 1)
    {
        //建立节点 s
        auto s = new LNode<E>;
        s->data = e;
        //在 p 之后插入 s
        s->next = p->next;
        p->next = s;
    }
    else
    {
        throw "Invalid i";
    }
}

///链表删除
template <typename E>
void ListDelete(LinkList<E> &L, int i, E &e)
{
    //查找第 i - 1 的节点p
    auto p = L;
    int j = 0;
    while (p && j < i - 1)
        p = p->next, ++j;

    //若找到第i个节点，则删除 ，抛出异常
    if (p && j == i - 1 && p->next)
    {
        auto q = p->next;
        e = q->data;
        //删除第 i 个数据节点
        p->next = q->next;
        delete q;
    }
    else
    {

        throw "Invalid i";
    }
}
